/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        // memset对于4byte的int，会赋值成
        // 00000001 00000001 00000001 00000001
        // = 16843009

        // 对于不是1byte的只能赋0

        // memset(rowCharAvailiable_, 1, 81*sizeof(int));
        // memset(colCharAvailiable_, 1, 81*sizeof(int));
        // memset(blockCharAvailiable_, 1, 81*sizeof(int));

        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                rowCharAvailiable_[i][j] = 1;
                colCharAvailiable_[i][j] = 1;
                blockCharAvailiable_[i][j] = 1;
            }
        }

        // init
        for (int row=0;row<9;row++){
            for (int col=0;col<9;col++){
                char cell = board[row][col];
                if (cell == '.'){continue;}
                
                int charIndex = cell - '1';
                // col
                colCharAvailiable_[col][charIndex] = 0;
                // row
                rowCharAvailiable_[row][charIndex] = 0;
                // block
                blockCharAvailiable_[insideBlockIndex(row, col)][charIndex] = 0;
            }
        }

        // start trace back
        traceBack(board, 0, 0);

        return;
    }
private:
    bool traceBack(vector<vector<char>>& board, int row, int col){
        // 其实不需要按照行列顺序走，可以直接dfs走
        for (int i=row;i<9;i++){
            for (int j=0;j<9;j++){
                if (board[i][j] != '.'){continue;}

                // to be filled
                for (int charIndex=0;charIndex<9;charIndex++){
                    if (isValidChar(charIndex, i, j)){
                        // change status
                        changeStatus(board, charIndex, i, j);

                        if (traceBack(board, i, j)){
                            // success
                            return true;
                        }
                        // resume status
                        resumeStatus(board, charIndex, i, j);
                    }
                }
                // no candidate succeed
                return false;
            }
        }
// printf("sucess (%d %d)\n", row, col);
// plotMatrix(board);
        return true;
    }
    void changeStatus(vector<vector<char>>& board, int charIndex, int row, int col){
        board[row][col] = charIndex + '1';
        colCharAvailiable_[col][charIndex] = 0;
        rowCharAvailiable_[row][charIndex] = 0;
        blockCharAvailiable_[insideBlockIndex(row, col)][charIndex] = 0;
    }
    void resumeStatus(vector<vector<char>>& board, int charIndex, int row, int col){
        board[row][col] = '.';
        colCharAvailiable_[col][charIndex] = 1;
        rowCharAvailiable_[row][charIndex] = 1;
        blockCharAvailiable_[insideBlockIndex(row, col)][charIndex] = 1;
    }
private:
    // no need to use set
    // use array instead
    int colCharAvailiable_[9][9];
    int rowCharAvailiable_[9][9];
    int blockCharAvailiable_[9][9];
private:
    inline bool isValidChar(int charIndex, int row, int col){
        return colCharAvailiable_[col][charIndex] == 1 and
               rowCharAvailiable_[row][charIndex] == 1 and
               blockCharAvailiable_[insideBlockIndex(row, col)][charIndex] == 1;
    }
    // 0 1 2
    // 3 4 5
    // 6 7 8
    inline int insideBlockIndex(int row, int col){
        return 3*(row/3) + (col/3);
    }
    // void plotMatrix(vector<vector<char>>& res){
    //     printf("-----------------\n");
    //     for (int i=0;i<res.size();i++){
    //         for (int j=0;j<res[0].size();j++){
    //             printf("%c ", res[i][j]);
    //         }
    //         printf("\n");
    //     }
    //     printf("-----------------\n");
    // }
};
// @lc code=end

int main(){
    vector<vector<char>> testCase = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };
    Solution test;
    test.solveSudoku(testCase);
}